package com.itheima.algorithm.exhaustion;

import java.util.concurrent.atomic.AtomicInteger;

/**
 * <h3>零钱兑换</h3>
 */
public class Leetcode322 {
    static int min = -1; // 需要的最少硬币数  2 3

    public int coinChange(int[] coins, int amount) {
        rec(0, coins, amount, new AtomicInteger(-1));
        return min;
    }

    // count 代表某一组合 钱币的总数
    public void rec(int index, int[] coins, int remainder, AtomicInteger count) {
        count.incrementAndGet(); // count++
        if (remainder == 0) {
            if (min == -1) {
                min = count.get();
            } else {
                min = Integer.min(min, count.get());
            }
        } else if (remainder > 0) {
            for (int i = index; i < coins.length; i++) {
                rec(i, coins, remainder - coins[i], count);
            }
        }
        count.decrementAndGet(); // count--
    }

    public static void main(String[] args) {
        Leetcode322 leetcode = new Leetcode322();
        System.out.println(leetcode.coinChange(new int[]{2}, 3));
    }
}
